use std::collections::{BTreeMap, HashMap};
use std::fmt::{Display, Formatter, Result};

pub struct Roman {
    chars: Vec<String>,
}

impl Display for Roman {
    fn fmt(&self, _f: &mut Formatter<'_>) -> Result {
        let string = self.chars.concat();
        _f.write_str(string.as_str())
    }
}

impl From<u32> for Roman {
    fn from(num: u32) -> Self {
        let mut tmp = num;
        let mut chars = Vec::new();
        let mut map = BTreeMap::new();
        map.insert(1000, "M");
        map.insert(900, "CM");
        map.insert(500, "D");
        map.insert(400, "CD");
        map.insert(100, "C");
        map.insert(90, "XC");
        map.insert(50, "L");
        map.insert(40, "XL");
        map.insert(10, "X");
        map.insert(9, "IX");
        map.insert(5, "V");
        map.insert(4, "IV");
        map.insert(1, "I");

        let mut counter = HashMap::new();

        while tmp > 0 {
            for (n, &roman) in map.range(..=tmp).rev() {
                let count = counter
                    .entry(roman)
                    .and_modify(|v| *v += 1)
                    .or_insert(1);
                if *count <= 3 {
                    chars.push(String::from(roman));
                    tmp -= n;
                    break;
                }
            }
        }
        Roman { chars }
    }
}

#[test]
#[ignore]
fn number_141_is_cxli() {
    let input = 141;
    let output = Roman::from(input).to_string();
    let expected = "CXLI";
    assert_eq!(output, expected);
}
